Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[ [2],[1],[1,2,2],[2,2],[1,2],[]]

题目大意：给定一个包含重复数字的数组，返回其所有的子集

题目难度：Medium

import java.util.*;
/**
 * Created by gzdaijie on 16/6/4
 * 对于每一位数字,每个子集可以选择包含或不包含
 * 对于重复的数字,特殊处理,即看作是一个整体.
 * 例如1,2,2 处理到2时,有三种情况,包含[],包含[2],包含[2,2]共三种情况
 */
public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Queue<List<Integer>> result = new LinkedList<>();
        int[] flag = new int[nums.length];

        Arrays.sort(nums);
        result.add(new ArrayList<Integer>());

        /**
         * 移除nums中重复的数字,flag记录每个位置数字出现的次数
         */
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == nums[k]) {
                flag[k]++;
            } else {
                flag[++k] = 1;
                nums[k] = nums[i];
            }
        }

        /**
         * 对于k个数,每个子集选择包含或不包含
         * 一个数字如果出现了j次,那么就有j+1种包含的可能,分别是[],[x],[x,x],[x...x]
         */
        for (int i = 0; i <= k; i++) {
            int size = result.size();
            while (size-- > 0) {
                List<Integer> top = result.poll();
                List<Integer> top_copy;
                result.add(top);
                for (int j = 0; j < flag[i]; j++) {
                    top_copy =  (List<Integer>) ((ArrayList<Integer>) top).clone();

                    for (int l = 0; l <= j; l++) top_copy.add(nums[i]);
                    result.add(top_copy);
                }
            }
        }
        return (List<List<Integer>>)result;
    }
}